package BFS解决FloodFill算法.解决拓扑排序;

import java.util.*;

public class 课程表二 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {

       // 1. 准备工作
        List<List<Integer>> edges =  new ArrayList<>();// 用邻接表来存储图
        for(int i = 0 ;i<numCourses;i++)
        {
            edges.add(new ArrayList<>());
        }
        int [] in  = new int[numCourses];

        // 2. 建图
        for(int i = 0 ;i<prerequisites.length;i++)
        {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            edges.get(b).add(a);
            in[a]++;
        }

        //3.拓补排序
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0;i<numCourses;i++)
        {
            if(in[i] == 0)
            {
                q.add(i);
            }
        }
        List <Integer> res = new ArrayList<>();
        int [] ret = new int[numCourses];
        int index =0;
        while(!q.isEmpty())
        {
            int cur = q.poll();
            ret[index++] = cur;

            for(int next:edges.get(cur))
            {
                in[next]--;
                if(in[next] == 0)
                {
                    q.add(next);
                }
            }

        }

        return ret.length == numCourses ? ret : new int[]{};
    }
}
